package com.xinpan.exercise;

public class ReverseKGroup {
    public ListNode reverseKGroup(ListNode head, int k) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(k == 1)  
            return head;
            
        ListNode newH = new ListNode(-1);
        newH.next = head;
        ListNode pre = newH;
        
        while(true)
        {
            ListNode cur = pre.next;
            for(int i = 1; cur!= null && i < k; i++)
                cur = cur.next;
                
            if(cur == null)
                return newH.next;
            
            ListNode tail = cur.next;
            ListNode h = pre.next;
            pre.next = reverse(pre.next, k, tail);
            pre = h;
        }
    }
    
    public ListNode reverse(ListNode head, int k, ListNode tail)
    {
        ListNode cur = head.next;
        head.next = tail;
        
        for(int i = 1; i < k; i++)
        {
            ListNode h = cur.next;
            cur.next = head;
            head = cur;
            cur = h;
        }
        return head;
    }
}
